import java.util.LinkedList;
import java.util.Queue;

/**
 * @author ZJX
 * @version 1.0
 * @descption 图论相关必会题
 * @since 2025/11/1 12:21
 */
public class Graph {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int row = grid.length;
        int col = grid[0].length;
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j, row, col);
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int i, int j, int row, int cow) {
        if (i < 0 || i >= row || j < 0 || j >= cow || grid[i][j] != '1') {
            return;
        }
        grid[i][j] = '0';  // 标记成陆地表示已访问

        dfs(grid, i - 1, j, row, cow);
        dfs(grid, i + 1, j, row, cow);
        dfs(grid, i, j - 1, row, cow);
        dfs(grid, i, j + 1, row, cow);
    }

    public int maxAreaOfIsland(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int row = grid.length;
        int col = grid[0].length;
        int maxArea = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1) {
                    int curArea = dfsA(grid, i, j, row, col);
                    maxArea = Math.max(maxArea, curArea);
                }
            }
        }
        return maxArea;
    }

    private int dfsA(int[][] grid, int i, int j, int row, int col) {
        if (i < 0 || i >= row || j < 0 || j >= col || grid[i][j] != 1) {
            return 0;
        }
        grid[i][j] = 0;  // 标记成陆地表示已访问

        return 1 + dfsA(grid, i - 1, j, row, col)
                + dfsA(grid, i + 1, j, row, col)
                + dfsA(grid, i, j - 1, row, col)
                + dfsA(grid, i, j + 1, row, col);
    }

    /**
     * 岛屿数量的 BFS版本
     *
     * @param grid 岛屿
     * @return 数量
     */
    public int numIslandsBFS(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int row = grid.length;
        int col = grid[0].length;
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    bfs(grid, i, j, row, col);
                }
            }
        }
        return count;
    }

    private void bfs(char[][] grid, int i, int j, int row, int col) {
        Queue<int[]> queue = new LinkedList<>(); // 存储待访问的陆地坐标（[i,j]）
        queue.offer(new int[]{i, j});
        grid[i][j] = '0';
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int x = poll[0];
            int y = poll[1];
            for (int[] dir : dirs) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                if (nx >= 0 && nx < row && ny >= 0 && ny < col && grid[nx][ny] == '1') {
                    queue.offer(new int[]{nx, ny});
                    grid[nx][ny] = '0';
                }
            }
        }
    }

    /**
     * 岛屿的最大面积 BFS版本
     *
     * @param grid 岛屿
     * @return 最大面积
     */
    public int maxAreaOfIslandBFS(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int row = grid.length;
        int col = grid[0].length;
        int maxArea = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1) {
                    int curArea = bfsA(grid, i, j, row, col);
                    maxArea = Math.max(maxArea, curArea);
                }
            }
        }
        return maxArea;
    }

    private int bfsA(int[][] grid, int i, int j, int row, int col) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, j});
        grid[i][j] = 0;
        int area = 1;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int x = poll[0];
            int y = poll[1];
            for (int[] dir : dirs) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                if (nx >= 0 && nx < row && ny >= 0 && ny < col && grid[nx][ny] == 1) {
                    queue.offer(new int[]{nx, ny});
                    grid[nx][ny] = 0;
                    area++;
                }
            }
        }
        return area;
    }

    /* ----------------------------------------- * --------------------------------------------------*/
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) {
            return -1;
        }
        if (n == 1) {
            return 1;
        }
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] vis = new boolean[n][n];
        queue.offer(new int[]{0, 0, 1});
        vis[0][0] = true;
        int[][] dirs = {
                {-1, 0},   // 上
                {1, 0},    // 下
                {0, -1},   // 左
                {0, 1},    // 右
                {-1, -1},  // 左上
                {-1, 1},   // 右上
                {1, -1},   // 左下
                {1, 1}     // 右下
        };
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int x = poll[0], y = poll[1], len = poll[2];
            if (x == n - 1 && y == n - 1) {
                return len;
            }

            for (int[] dir : dirs) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0 && !vis[nx][ny]) {
                    vis[nx][ny] = true;
                    queue.offer(new int[]{nx, ny, len + 1});
                }
            }
        }
        return -1;
    }
}

